package kyssion.leetcode.num51_100;

public class code91_解码方法 {
    public static void main(String[] args) {
        System.out.println(new code91_解码方法().numDecodings2("10100"));
    }

    public int numDecodings(String s) {
        if (s.length() <= 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        return ans(chars, chars.length - 1);
    }

    public int ans(char[] chars, int end) {
        if (end <= 0) {
            return 1;
        }
        if (chars[end] == '0') {
            return ans(chars, end - 1);
        }
        return ans(chars, end - 1) +
                ((chars[end - 1] <= '1' || chars[end - 1] <= '2' && chars[end] <= '6') ? ans(chars, end - 2) : 0);
    }


    public int numDecodings2(String s) {
        if (s == null || s.length() == 0) return 0;
        if (s.startsWith("0")) return 0;
        int length = s.length();
        int[] dp = new int[length];
        dp[0] = 1;
        for (int i = 1; i < length; i++) {
            if (s.charAt(i) != '0') dp[i] += dp[i - 1];
            if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6'))
                dp[i] += i >= 2 ? dp[i - 2] : 1;
        }
        return dp[length - 1];
    }
}
